perm filename DBL2.TEX[AM,DBL] blob
sn#543018 filedate 1980-11-19 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00009 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \init{
C00003 00003 \chapbegin{2} % Here beginneth Chapter 2
C00006 00004 \sectionbegin[1]{DISCUSSION OF THE AM PROGRAM}
C00012 00005 \subsectionbegin[1.2]{Agenda and Heuristics}
C00023 00006 \sectionbegin[2]{WHAT (NOT) TO GET OUT OF THIS EXAMPLE}
C00028 00007 \sectionbegin[3]{DECIPHERING THE EXAMPLE}
C00036 00008 \sectionbegin[4]{THE EXAMPLE ITSELF}
C00059 00009 \sectionbegin[5]{RECAPPING THE EXAMPLE}
C00064 ENDMK
C⊗;
\init{
\input cmpdes
\input ammacs
\def\draft{T}
\titlepage
\newpage
\setcount0 15
\parttitle{AM: DISCOVERY IN MATHEMATICS AS HEURISTIC SEARCH}
}
\baselineskip 12pt
\chapbegin{2} % Here beginneth Chapter 2
\chaptertitle{EXAMPLE: DISCOVERING PRIME NUMBERS}
\rjustline{\:B Example:}
\rjustline{\:B Discovering}
\rjustline{\:B Prime Numbers}
\runningrighthead{INTRODUCTION}
\tenpoint
\vskip 10pc
\noindent
This chapter will present an example of {\AM} in action, an excerpt from
the output of {\AM}, as it investigates some concepts.
After a brief discussion of {\AM}'s control structure in Section 2--1,
the reader will be told what the point of this example is---and Section
2--2 explains what it is
{\sl not}. Section 2--3 provides a few eleventh-hour hints at decoding
the example.
The excerpt itself follows in Section 2--4. It skips the first
half of the session, and picks up at a point just after {\AM} has defined the
concept ``Divisors-of.'' Soon afterward, {\AM} defines Primes, and begins
to find interesting conjectures related to them. The excerpt goes on
to show how {\AM} conjectured the fundamental theorem of arithmetic and
Goldbach's conjecture. {\AM} derived the notion of partitioning a
collection of $n$ objects into smaller bundles, but failed to find any
interesting conjectures about that process. Instead, {\AM} was
side-tracked into the (probably) fruitless investigation of numbers
which can be represented as the sum of two primes in one unique way.
The final section of this chapter will recap this example the way a
math historian might report it.
\vfill\eject
\sectionbegin[1]{DISCUSSION OF THE AM PROGRAM}
\par\vskip -18pt
\subsectionbegin[1.1]{Representation}
{\AM} is a program which expands a knowledge base of mathematical
concepts. Each concept is stored as a particular kind of data
structure, namely as a collection of properties or ``facets'' of the
concept. For example, here is a miniature example of a
\ffootnote{concept:}{The right arrow (``$\→$'') is the symbol for ``implies.''
``Nos.'' is an abbreviation for ``Numbers.'' The vertical bar ``$\relv $'' is a
symbol for the predicate ``divides evenly into;'' with a slash through it
(``$\not\,\ \relv\,\ $'') we denote ``does {\sl not} divide evenly into.''
``$\otimes $'' indicates exclusive
or, and the symbol ``$\forall $'' is read ``for all.'' }\par
\sectionskip
{\yskip \parskip 1pt \:r
\hbox{\ \ \ NAME: {\it Prime Numbers}}
\hbox{\ \ \ DEFINITIONS:}
\hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ ORIGIN: {\it Number-of-divisors-of(x) = 2 }}
\hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ PREDICATE--CALCULUS: $Prime(x) \↔ (\forall z) (z\relv x \→ (z=1 \otimes z=x))$}
\hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ ITERATIVE: $(for\ x>1): For\ i\ from \ 2 \ to\ \sqrt{x},\ i{\not\,\,\relv\,}\ x $ }
\hbox{\ \ \ EXAMPLES: $2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17$ }
\hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ BOUNDARY: $2,\ 3$ }
\hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ BOUNDARY--FAILURES: $0,\ 1$ }
\hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ FAILURES: $ 12$ }
\hbox{\ \ \ GENERALIZATIONS: {\it Nos., Nos. with an even no. of divisors}}
\hbox{\ \ \ SPECIALIZATIONS: {\it Odd Primes,\ Prime Pairs,\ Prime Uniquely--addables }}
\hbox{\ \ \ CONJECS: {\it Unique factorization,\ Goldbach's conjec.,\ Extrema of No--of--divisors--of }}
\hbox{\ \ \ INTU'S: {\it A metaphor to the effect that Primes are the building blocks of all numbers} }
\hbox{\ \ \ ANALOGIES: }
\hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ {\it Maximally--divisible numbers are converse extremes of Number--of--divisors--of }}
\hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ {\it Factor a non--simple group into simple groups }}
\hbox{\ \ \ INTEREST: {\it Conjectures tying Primes to Times,\ to Divisors--of,\ to related operations }}
\hbox{\ \ \ WORTH: $800$}}
\yskip
\noindent ``Creating a new concept'' is a well-defined activity: it involves
setting up a new data structure like the one above, and filling in
entries for some of its facets or slots. Filling in a particular
facet of a particular concept is also quite well-defined, and is
accomplished by executing a collection of relevant heuristic rules.
This process will be described in great detail in later chapters.
\subsectionbegin[1.2]{Agenda and Heuristics}
An agenda of plausible tasks is maintained by {\AM}. A typical task is
{\bf ``Fill-in examples of Primes.''} The agenda may contain hundreds of
entries such as this one. {\AM} repeatedly selects the top task from the
agenda and tries to carry it out. This is the whole control
structure! Of course, we must still explain how {\AM} creates plausible
new tasks to place on the agenda, how {\AM} decides which task will be
the best one to execute next, and how it carries out a task.
If the task is {\bf ``Fill-in new Algorithms for Set-union,''} then
{\sl satisfying} it would mean actually synthesizing some new procedures,
some new LISP code capable of forming the union of any two sets.
A heuristic rule is {\sl relevant} to a task if and only if executing
that rule brings {\AM} closer to satisfying that task.
Relevance is determined {\sl a priori} by where the rule
is stored. A rule tacked onto the Domain/range facet of the Compose
concept would be presumed relevant to the task {\bf ``Check the Domain/range
of Insert$\circ$Delete.''}
Once a task is chosen from the agenda, {\AM} gathers some heuristic
rules which might be relevant to satisfying that task. They are
executed, and then {\AM} picks a new task. While a rule is executing,
three kinds of actions or effects can occur:\par
\listbegin
\numlistentry[1]{Facets of some concepts can get filled in (\eg,
examples of
primes may actually be found and tacked onto the ``Examples'' facet of
the ``Primes'' concept). A typical heuristic rule which might have
this effect is:}
\yskip
\indentedline[20pt]{{\it To fill in examples of X, where X is a kind of Y
(for some more general concept Y),}}
\indentedline[20pt]{{\it Check the examples of Y; some of them may be examples
of X as well.}}
\yskip
\noindent
For the task of filling in examples of Primes, this rule would have
{\AM} notice that Primes is a kind of Number, and therefore look over
all the known examples of Number. Some of those would be primes, and
would be transferred to the Examples facet of Primes.
\numlistentry[2]{New concepts may be created (\eg, the concept ``primes which
are uniquely representable as the sum of two other primes'' may be somehow
be deemed worth studying). A typical heuristic rule which might
result in this new concept is:}
\yskip
\indentedline[20pt]{{\it If some (but not most) examples of X are also
examples of Y (for some concept Y),}}
\indentedline[20pt]{{\it Create a new concept defined as the intersection of
those 2 concepts (X and Y).}}
\yskip
\noindent
Suppose {\AM} has already isolated the concept of being representable as
the sum of two primes in only one way ({\AM} actually calls such numbers
``Uniquely-prime-addable numbers''). When {\AM} notices that some primes
are in this set, the above rule will create a brand new concept,
defined as the set of numbers which are both prime and uniquely prime
addable.
\numlistentry[3]{New tasks may be added to the agenda (\eg, the current
activity may suggest that the following task is worth considering:
{\bf ``Generalize the concept of prime numbers''}). A typical heuristic rule
which might have this effect is:}
\yskip
\indentedline[20pt]{{\it If very few examples of X are found,}}
\indentedline[20pt]{{\it Then add the following task to the agenda:
{\bf ``Generalize the concept X.''}}}
\yskip
\noindent\baselineskip 11pt
Of course, {\AM} contains a precise meaning for the phrase ``very few.''
When {\AM} looks for primes among examples of already-known kinds of
numbers, it will find dozens of non-examples for every example of a
prime it uncovers. ``Very few'' is thus naturally implemented as a
statistical confidence \ffootnote{level.}{The ratio of examples found to non-examples
stumbled over lies between .001 and .05. Philosophers outraged by this may
be somewhat appeased by knowledge that large changes in the precise
numbers very rarely alter {\AM}'s behavior.}
\listend
The concept of an agenda is certainly not new: schedulers have been
around for a long time. But one important feature of {\AM}'s agenda
scheme {\sl is} a new idea: attaching---and using---a list of
\ffootnote{quasi-symbolic}{Each reason is an English sentence. While {\AM}
can tell whether two given reasons coincide,
it can't actually do any internal processing on them. If this lack of intelligence
had proved to be a limiting problem,
then more work would have been expended on giving {\AM} some
such abilities.} reasons to each task which explain why the task is worth
considering, why it's plausible. {\sl It is the responsibility of the
heuristic rules to include reasons for any tasks they}
\footnote{{\sl propose\/}.}{An alternative scheme, perhaps even a bit more human-like, would be to
(perhaps only occasionally) allow a burst of poorly-motivated tasks to be
proposed, and then use some pruning criteria to weed out the obvious losers.
During this time, {\AM} could type out to the user (who otherwise would be closely
monitoring its activities) a cute anthropomorphic phrase like ``I'm
now sitting back and puffing on my pipe, lost in contemplation.''}
For example, let's reconsider the heuristic rule mentioned in (3)
above. It really looks more like the following:\par\ninepoint
\yskip
\indentedline[20pt]{{\sl If very few examples of X are found,}}
\hangindent 20pt after 0\noindent{{\sl Then add the following task to the agenda:
{\bf ``Generalize the concept X,''} for the following reason: ``X's are
quite rare; a slightly less restrictive concept might be more interesting.''}}
\yskip
\tenpoint\noindent
If the same task is proposed by several rules, then several different
reasons for it may be present. In addition, one ephemeral reason
also exists: ``Focus of attention.'' Any tasks which are similar to the
one last executed get ``Focus of attention'' as a bonus reason. {\AM}
uses all these reasons to decide how to rank the tasks on the
agenda. The ``intelligence'' {\AM} exhibits is not so much ``what it
does,'' but rather the {\sl order} in which it arranges its \footnote{agenda.}{For
example, alternating a randomly-chosen task and the ``best'' task (the
one {\AM} chose to do) only slows the system down by a factor of 2, yet
it totally destroys its credibility as a rational researcher
(as judged by the human user of {\AM}). This
is one conclusion of experiment 4 (see Section 5--4).}
{\AM} uses the list of
reasons in another way: Once a task has been selected, the quality of
the reasons is used to decide how much time and space the task will
be permitted to absorb, before {\AM} quits and moves on to a new task.
This whole mechanism will be detailed in Section 3--2.
\sectionskip
\sectionbegin[2]{WHAT (NOT) TO GET OUT OF THIS EXAMPLE}
The purpose of the example which comprises the next subsection is to
convey a bit of {\AM}'s flavor. After reading through it, the reader
should be convinced that {\AM} is {\sl not} a theorem prover, nor is {\AM}
{\sl randomly} manipulating entries in a knowledge base, nor is it
{\sl exhaustively} manipulating or searching. {\AM} is carefully growing a network
of data structures representing mathematical concepts, by repeatedly
using heuristics both (a) for guidance in choosing a task to work on next and
(b) for providing methods to satisfy the chosen task.
The following points are important but can't be conveyed by any lone
example:
\listbegin
\numlistentry[1]{Although {\AM} appears to have reasonable natural language
abilities, this is a typical AI illusion: most of the phrases {\AM}
types are mere tokens, and the syntax which the user must obey is
unnaturally constrained. For the sake of clarity, I have ``touched up''
some of the wording, indentation, syntax, etc., of what {\AM} actually
outputs, but left the spirit of each phrase intact. As the reader
becomes more familiar with {\AM}, future examples can be ``unretouched.''
If it is desired, the reader may glance at Appendix 3--2,
which shows some actual listings of {\AM} in action.}
\numlistentry[2]{The reader should be skeptical
of the generality of the
program; is the knowledge base ``just right'' (\ie, finely tuned to
elicit this one chain of behaviors)?
The answer is \ffootnote{``{\sl No}.''}{The
{\sl design} of {\AM} was finely tuned so that the answer to this question
would be ``{\sl No}.'' Ponder that one!} The whole point of this project is
to show that a relatively small set of general heuristics can guide a
nontrivial discovery process. Each activity, each task, was proposed
by some heuristic rule (like ``look for extreme cases of X'') which was
used time and time again, in many situations. It was not considered
fair to insert heuristic guidance which could ``guide'' only in a
single situation.}
\listend
This kind of generality can't be shown convincingly in one example.
Never\-the\-less, even within this small excerpt, the same line of
development which leads to decom\-posing num\-bers (using Times\inv ),
there\-by dis\-co\-ver\-ing unique fac\-tori\-za\-tion, also leads to decomposing
numbers (using Add\inv ), thereby dis\-covering Goldbach's conjec\-ture.
The same heuristic which caused {\AM} to ex\-pect that unique
factorization would be useful, also caused {\AM} to sus\-pect that
Goldbach's conjecture would be useless.
\yskip
Let me reemphasize that the point of this example is {\sl not} the
specific mathematical concepts, nor the particular chains of
plausible reasoning {\AM} produces, nor the few flashy conjectures {\AM}
spouts, but rather an illustration of the {\sl kinds} of things {\AM}
does.
\sectionskip
\sectionbegin[3]{DECIPHERING THE EXAMPLE}
Recall that, in general, each task on the agenda will have several
reasons attached to it. In the example excerpt, the reasons for each
task are printed just after the task is chosen and before it is
executed.
{\AM} numbers its activities sequentially. Each time a new task is chosen, a counter
is incremented. The first task in the example excerpt is labelled
\understep{{\sl Task 65}}, meaning that the example skips the first 64 tasks which
{\AM} selects and carries out.
The reason simply is that the development of simple concepts related to
divisibility will probably be more intelligible and palatable to the reader
than {\AM}'s early ramblings in finite set theory.
\def\GAPPAGE{\count0}
In the example itself, several irrelevant tasks have been
\footnote{excised.}{This is fair, despite the results of Experiment 5 (see
Section 5--3.5) because the remaining
tasks clump together in twos, threes, etc; they are uninterrupted
lines of research (for example, Tasks 65--67) separated by very large
gaps
(for example, the jump from Task 68 to 79).} About half of those omitted
tasks were interesting in themselves, but all of them were tangential
or unrelated to the development shown. The reader can tell by the
global task numbering how many were skipped. For example, notice
that the excerpt jumps from Task 67 to Task 79.
To help gauge {\AM}'s abilities, the reader may be interested to know
that {\AM} defined ``Natural Numbers'' during Task 32, and ``Times'' was
defined during Task 122. {\AM} started with no knowledge of numbers, and
only scanty knowledge of sets and set-operations. Task 2, \eg, was to
fill in examples of Sets.
The concepts that {\AM} talks about are self-explanatory---by and
large. The following are some nonstandard concepts (whenever
there is a conflict between ``computer science jargon'' and ``math
jargon,'' I have opted for the latter; \eg, all ``functions'' are
necessarily single-valued for each member of their domain):
\listbegin
\hddlistentry[BAG]{is a kind of list structure, a bunch of elements which
are unordered, but one in which multiple copies of the same element
are permitted. One may visualize a paper bag filled with cardboard
letters. Technically, we shall say that a set is {\sl not} considered
to be a bag. A bag is denoted by enclosure within parentheses, just
as sets are within braces. So the bag containing X and four Y's might
be written (X Y Y Y Y), and would be considered indistinguishable
from the bag (Y Y Y X Y).}
\hddlistentry[Number]{will mean (typically) a positive integer.}
\hddlistentry[Times\inv]{is a particular relation. For any number x,
Times$\minv(x)$ is a set of bags. Each bag contains some numbers which,
when multiplied together, equal $x$. For example,
Times$\minv (18) = \{ (18)$ (2 9) (2 3 3) (3 6)$\}$. Checking, we see that
multiplying the numbers in the bag (2 3 3) together, we do get
$2\times 2\times 3 = 18$. Times$\minv(x)$ contains all possible such bags
(containing natural numbers $>1$).}
\hddlistentry[Add\inv]{is a relation analogous to Times\inv. For any number $x$,
Add$\minv(x)$ is also a set of bags. Each bag contains a bunch of
numbers which, when added together, equal $x$. For example,
Add$\minv(4) = \{ (4)$ (1 1 1 1) (1 1 2) (1 3) (2 2)\penalty 1000$\}$.
Add$\minv(x)$ contains all
possible such bags (containing numbers $>0$); it finds all possible
{\sl partitions} of $x$.}
\hddlistentry[Divisors-of]{is a more standard relation. For any number $x$,
Divisors-of$(x)$ is the set of all positive numbers which divide evenly
into $x$. For example, Divisors-of$(18) = \{$1 2 3 6 9 18$\}$.}
% \listend
\baselineskip 12pt
\sectionskip
\sectionbegin[4]{THE EXAMPLE ITSELF}
{\AM} is an {\sl interactive} computer program. It prints out phrases
indicating what it is doing at each moment, and a human being,
referred to as the {\sl User}, watches {\AM}'s activities. At any moment,
the user can interrupt {\AM} to ask questions or re-direct its energies.
In the excerpt, the user never re-directs {\AM}, although he or she does
occasionally ask {\AM} to rename some concept and to explain its
behavior (\eg, just after \understep{{\sl Task\ 106}}). For the benefit of the
reader, I have prefaced all the user's comments by ``{\tt USER:},''
and italicized my {\sl post hoc} annotations.
{\eightpoint \:> \parskip 1pt \lineskip 1pt \parindent 0pt
\threstar{Task\ 65}
Filling in examples of the following concept: ``Divisors-of.''
3 Reasons:
\indentedline[20pt]{(1) No known examples for Divisors-of so far.}
\indentedline[20pt]{(2) Times, which is related to Divisors-of, is
now very interesting.}
\indentedline[20pt]{(3) Focus of attention: {\AM} recently defined Divisors-of.}
26 examples found, in 9.2 seconds. \eg: Divisors-of$(6)=\{1\ 2\ 3\ 6\}$.
\threstar{Task\ 66}
Considering numbers which have very small sets of Divisors-of
(\ie, very few divisors).
2 Reasons:
\indentedline[20pt]{(1) Worthwhile to look for extreme cases.}
\indentedline[20pt]{(2) Focus of attention: {\AM} recently worked on Divisors-of.}
Filling in examples of numbers with 0 divisors.
0 examples found, in 4.0 seconds.
Conjecture: no numbers have 0 divisors.
Filling in examples of numbers with 1 divisors.
1 examples found, in 4.0 seconds. e.g.: Divisors-of$(1)=\{1\}$.
Conjecture: 1 is the only number with 1 divisor.
Filling in examples of numbers with 2 divisors.
24 examples found, in 4.0 seconds. e.g.: Divisors-of(13)=$\{$1 13$\}$.
No obvious conjecture. This kind of number merits more study.
Creating a new concept: ``Numbers-with-2-divisors.''
}% end of \eightpoint, etc.
\yskip
{\hangindent 20pt after 0 {\sl {\AM} had previously derived the notion
of singleton, doubleton, etc.
Above, {\AM} was actually defining the set of numbers which gets
mapped into a doubleton of numbers by the operation Divisors-of.
I took the liberty of translating this into the above form, which uses
the numeral ``2.''}}
\yskip
{\eightpoint \:> \parskip 1pt \lineskip 1pt \parindent 0pt
Filling in examples of numbers with 3 divisors.
11\ examples found, in 4.0 seconds. e.g.: Divisors-of$(49)=\{1\ 7\ 49\}$.
All numbers with 3 divisors are also Squares. This kind of number
merits more study.
Creating a new concept: ``Numbers-with-3-divisors.''
}
\yskip
{\hangindent 20pt after 0 {\sl How did {\AM} notice that conjecture?
t took a random example of Numbers-with-3-divisors,
say, 49. Then it asked what other known concepts ``49'' was an example of.
The two answers were: Odd-numbers and Perfect-squares. {\AM} then tested these
conjectures on the other ten examples just found. The only surviving conjecture
was that all numbers-with-3-divisors are also perfect-squares.}}
\yskip
{\eightpoint \:> \parskip 1pt \lineskip 1pt \parindent 0pt
\threstar{Task\ 67}
Considering the square-roots of Numbers-with-3-divisors.
2 Reasons:
\indentedline[20pt]{(1) Numbers-with-3-divisors are unexpectedly also perfect Squares.}
\indentedline[20pt]{(2) Focus of attention: {\AM} recently worked on
Numbers-with-3-divisors.}
All square-roots of Numbers-with-3-divisors seem to be Numbers-with-2-divisors.
e.g., Divisors-of$($Square-root$(169) ) =$ Divisors-of$(13) = \{1\ 13\}$.
Formulating the converse to this statement. Empirically, it seems to be true.
The square of each Number-with-2-divisors seems to be a Number-with-3-divisors.
This is very unusual. It is not plausibly a coincidence.
(Chance of coincidence is $<$.001)
Boosting interestingness factor of the concepts involved:
Interestingness factor of ``Divisors-of'' raised from 300 to 400.
Interestingness factor of ``Numbers-with-2-divisors'' raised from 100 to 600.
Interestingness factor of ``Numbers-with-3-divisors'' raised from 200 to 700.
\yskip
{\:q USER: Call the set of numbers with 2 divisors ``Primes.''}
\yskip
\threstar{Task\ 68}
Considering the squares of Numbers-with-3-divisors.
2 Reasons:
\indentedline[20pt]{(1) Squares of Numbers-with-2-divisors were interesting.}
\indentedline[20pt]{(2) Focus of attention: {\AM} recently worked on
Numbers-with-3-divisors.}
\indentedline[30pt]{$\vdots$}
}
\yskip
{\hangindent 20pt after 0 {\sl This gap in the sequencing---from Task
68 to Task 79---eliminates some
tangential and boring tasks. See page 19 for an explanation.}}
\yskip
{\eightpoint \:> \parskip 1pt \lineskip 1pt \parindent 0pt
\indentedline[30pt]{\ \ \ $\vdots$}
\threstar{Task\ 79}
Examining Times$\minv(x)$, looking for patterns involving its values.
2 Reasons:
\indentedline[20pt]{(1) Times\inv\ is related to the newly-interesting
concept ``Divisors-of.''}
\indentedline[20pt]{(2) Many examples of Times\inv\ are known, to induce from.}
Looking specifically at Times\inv(12), which is $\{ (12) (2\ 6) (2\ 2\ 3) (3\ 4) \}$.
13 conjectures proposed, after 2.0 seconds.
e.g., ``Times\inv(x) always contains a bag containing only even numbers.''
Testing the conjectures on other examples of Times\inv .
5 false conjectures deal with even numbers.
{\AM} will at some time consider the restriction of Times\inv\ to even numbers.
Only 2 out of the 13 conjectures are verified for all 26 known examples of
Times\inv :
Conjecture 1: Times\inv(x) always contains a singleton bag.
e.g., Times$\minv(12)$, which is $\{ (12) (2\ 6) (2\ 2\ 3) (3\ 4) \}$, contains $(12)$.
e.g., Times$\minv 13)$, which is $\{ (13) \}$, contains $(13)$.
Creating a new concept, ``Single-times.''
Single-times is a relation from Numbers to Bags-of-numbers.
Single-times$(x)$ is all bags in Times\inv(x) which are singletons.
e.g., Single-times$(12)=\{ (12) \}$.
e.g., Single-times$(13)=\{ (13) \}$.
Conjecture 2: Times\inv(x) always contains a bag containing only primes.
e.g., Times$\minv(12)$, which is $\{ (12) (2\ 6) (2\ 2\ 3) (3\ 4) \}$, contains $(2\ 2\ 3)$.
e.g., Times$\minv(13)$, which is $\{ (13) \}$, contains $(13)$.
Creating a new concept, ``Prime-times.''
Prime-times is a relation from Numbers to Bags-of-numbers.
Prime-times$(x)$ is all bags in Times\inv(x) which contain only primes.
e.g., Prime-times$(12)=\{ (2\ 3\ 3) \}$.
e.g., Prime-times$(13)=\{ (13) \}$.
\threstar{Task\ 80}
Considering the concept ``Prime-times.''
2 Reasons:
\indentedline[20pt]{(1) Conjecs about Prime-times will tell much about
Primes and Times\inv .}
\indentedline[20pt]{(2) Focus of attention: {\AM} recently defined Prime-times.}
Looking specifically at Prime-times$(48)$, which is $\{ (2\ 2\ 2\ 2\ 3) \}$.
4 conjectures proposed, after .6 seconds.
e.g., ``$x$ is never inside any member of Prime-times$(x)$.''
Testing them on other examples of Prime-times.
Only 1 out of the 4 conjectures are verified for all 23 known examples of Prime-times:
Conjecture 1: Prime-times$(x)$ is always a singleton set.
That is, Prime-times is a function, not just a relation.
e.g., Prime-times(48), which is $\{$ (2\ 2\ 2\ 2\ 3) $\}$, is a singleton set.
e.g., Prime-times(47), which is $\{$ (47) $\}$, is a singleton set.
This holds for all 17 known examples of Prime-times. (Chance of coincidence is .0001)
This fails for 2 of the boundary cases (extreme numbers): 0 and 1.
Conjecture is amended: Each number >1 is the product of a unique bag of primes.
I suspect that this conjecture may be very useful.
}
\yskip
{\hangindent 20pt after 0{\sl How did {\AM} know this? One of the
(unfortunately few!) meta-heuristics in {\AM} said the following:
``When using the {\rm `look at the inverse of extreme items under
the operation f'} rule,
Tack the following note onto the Interest facet of the new concept which is created:
{\rm `Conjectures involving this concept and f (or f\inv ) are natural, interesting, and
probably useful.'}''
Now the concept PRIMES was defined using the `extrema'
heuristic rule, with f$=$Divisors-of. When PRIMES was first created, the meta-rule
we just presented tacked the following note onto Primes.Interest:
{\rm ``Conjectures involving Primes and division (or multiplication)
are natural, interesting, and
probably useful.''} Thus the unique factorization conjecture triggers this feature,
whereas Goldbach's conjecture wouldn't. }}
{\eightpoint \:> \parskip 1pt \lineskip 1pt \parindent 0pt
\yskip
{\:q USER: Call this conjecture ``Unique factorization conjecture.''}
\vfill
\indentedline[30pt]{$\vdots$}
\vfill
}
{\hangindent 20pt after 0 {\sl To show that {\AM} isn't really always
right on the mark, the next sequence of
tasks includes a crime of omission (ignoring the concept of Partitions) and a
false start (worrying about numbers which can be represented as the sum of two
primes in precisely one way).
Notice the skip here; 3 tasks have been omitted.}}
\yskip
{\eightpoint \:> \parskip 1pt \lineskip 1pt \parindent 0pt
\threstar{Task\ 84}
Examining Add\inv (x), looking for patterns involving its values.
2 Reasons:
\indentedline[20pt]{(1) Add\inv\ is analogous to the newly-interesting concept ``Times\inv .''}
\indentedline[20pt]{(2) Many examples of Add\inv\ are known, to induce from.}
Looking specifically at Add\inv (6), which is $\{$ (1\ 1\ 1\ 1\ 1\ 1) (1\ 1\ 1\ 1\ 2) (1\ 1\ 1\ 3) (1\ 1\ 2\ 2)
(1\ 1\ 4) (1\ 2\ 3) (1\ 5) (2\ 2\ 2) (2\ 4) (3\ 3) (6)$\}$.
17 conjectures proposed, after 3.9 seconds.
e.g., ``Add\inv (x) always contains a bag of primes.''
Testing them on other examples of Add\inv .
Only 11 out of the 17 conjectures are verified for all 19 known examples of Add\inv :
3 out of the 11 conjectures were false until amended.
Conjecture 1: Add\inv (x) never contains a singleton bag.
Conjecture 2: Add\inv (x) always contains a bag of size 2 (also called a ``pair'' or a ``doubleton'').
e.g., Add\inv (6) contains (1\ 5), (2\ 4), and (3\ 3).
e.g., Add\inv (4) contains (1\ 3), and (2\ 2).
Creating a new concept, ``Pair-add.''
Pair-add is a relation from Numbers to Pairs-of-numbers.
Pair-add(x) is all bags in Add\inv (x) which are doubletons (\ie, of size 2).
e.g., Pair-add(12)=$\{$ (1\ 11) (2\ 10) (3\ 9) (4\ 8) (5\ 7) (6\ 6) $\}$.
e.g., Pair-add(4)=$\{$ (1\ 3) (2\ 2) $\}$.
Conjecture 3: Add\inv (x) always contains a bag containing only 1's.
\indentedline[40pt]{$\vdots$}
Conjecture 10: Add\inv (x) always contains a pair of primes.
This conjecture is false. Conjecture is amended:
``Add\inv (x) usually (but not always) contains a pair of primes.''
e.g., Add\inv (10) contains (3\ 7), and (5\ 5).
e.g., Add\inv (4) contains (2\ 2).
e.g., Add\inv (11) does not contain a pair of primes.
Creating a new concept, ``Prime-add.''
Prime-add is a relation from Numbers to Pairs-of-numbers.
Prime-add(x) is all bags in Add\inv (x) which are pairs of primes.
e.g., Prime-add(12)=$\{$ (5\ 7) $\}$.
e.g., Prime-add(10)=$\{$ (3\ 7) (5\ 5) $\}$.
e.g., Prime-add(11) = $\{$ $\}$
\indentedline[30pt]{$\vdots$}
\threstar{Task\ 106}
Considering the set of numbers for which Prime-add is defined (has non-empty value).
1 Reason:
\indentedline[20pt]{(1) Prime-add often has non-empty value. Worth isolating that case.}
Warning: no task\ on the agenda has an interestingness value above 200!!!
Creating a new concept ``Prime-addable.''
Prime-addable is a kind of Number. x is Prime-addable iff Prime-add(x) is non-empty.
Will spend 5.0 seconds filling in examples of Prime-addable.
18 examples found. Here are some of them: 4 5 6 7 8 9 10 12 13 14 17 16 18.
Empirically, all even numbers are also in this set (ignoring boundary cases: 0 2 4 6).
So conjectured. Danger: must examine boundary cases: the numbers 0, 2, 4, and 6.
Two exceptions noticed. The only exceptions are the smallest boundary cases: 0, 2.
Conjecture is amended: All even numbers >2 are the sum of two primes.
Warning: I expect this conjecture will be cute but useless.
\yskip
{\:q USER: Why?}
\yskip
Because the concept of ``Primes'' originally arose as extreme cases of Divisors-of.
The more closely an operation F is related to the concept Divisors-of, the more
natural will be any conjecture involving both that operation F and Primes.
\eg, conjectures involving both Primes and Times will be natural and useful.
But this conjecture, which involves Primes and Add\inv , will be cute but useless,
since the relation ``Add\inv '' is unrelated to the relation ``Divisors-of.''
End of explanation.
\vfill
\yskip
{\:q USER: Call this conjecture ``Goldbach's conjecture.''}
\yskip
\threstar{Task\ 107}
Considering the set of numbers for which the relation Prime-add is single-valued.
3 Reasons:
\indentedline[20pt]{(1) Prime-add often has singleton value. Worth isolating that case.}
\indentedline[20pt]{(2) Restricted to this set, Prime-add would be a function.}
\indentedline[20pt]{(3) Focus of attention: {\AM} recently worked on Prime-add.}
Creating a new concept ``Uniquely-prime-addable.''
``Uniquely-prime-addable'' is a kind of Number.
x is Uniquely-prime-addable iff Prime-add(x) is a singleton.
Will spend 10.0 seconds filling in examples of Uniquely-prime-addable.
11 examples found. Here are some of them: 4 5 7 8 9 12 13.
No obvious conjecture derived empirically.
Will forget ``Uniquely-prime-addable numbers,'' if no Ties found in near future.
}
\tenpoint \parindent 20pt
\sectionskip
\sectionbegin[5]{RECAPPING THE EXAMPLE}
Let's once again eavesdrop on a mathematician, who is describing to a
colleague what {\AM} did:
This example was preceded by the momentous discoveries of
multiplication and division. Several interesting properties of these
operations were noticed.
The first task illustrated (\understep{\sl Task\ 65})
involves exploring the concept of ``divisors of a number'' (meaning all
positive integers which divide evenly into the given number). After
tiring of finding examples of this relation, {\AM} investigates extreme
cases: that is, it wonders which numbers have very few or very many
divisors.
{\AM} thus discovers Primes in a curious way. Numbers with 0 or 1
divisor are essentially nonexistent, so they're not found to be
interesting. {\AM} notices that numbers with 3 divisors always seem to
be squares of numbers with 2 divisors (primes). This raises the
interestingness of several concepts, including primes. Soon
(\understep{\sl Task\ 79}),
another conjecture involving primes is noticed: Many numbers
seem to factor into primes. This causes a new relation to be defined,
which associates to a number $x$, all prime factorizations of $x$. The
first question {\AM} asks about this relation is ``is it a function?''
This question is the full statement of the unique factorization
conjecture: the fundamental theorem of arithmetic. {\AM} recognized the
value of this relationship, and assigned it a high interestingness rating.
In a similar manner, though with lower hopes, it noticed some more
relationships involving primes, including Goldbach's conjecture. {\AM}
quite correctly predicted that this would turn out to be cute but of
no future use mathematically.
The last activity mentioned (\understep{\sl Task\ 107}) shows {\AM} examining a
rather nonstandard concept: ``numbers which can be written as the sum
of a pair of primes, in only one way.'' These are termed
``uniquely-prime-addable'' numbers. It was mildly unfortunate that {\AM}
gave up on this concept before noticing that $p+2$ is
uniquely-prime-addable, for any prime number $p$, and that in fact
these are the only odd uniquely-prime-addable numbers. The session
was repeated once, with a human user telling {\AM} explicitly to
continue studying this concept. {\AM} did in fact construct
``Uniquely-prime-addable-odd-numbers,'' and then notice this
relationship. Here we see an example of unstable equilibrium: if
pushed slightly this way, {\AM} will get very interested and spend a lot
of time working on this kind of number. Since it doesn't have all the
sophistication (\ie, compiled hindsight) that we have, it can't know
instantly whether what it's doing will be fruitless.
\worldend